#include <iostream>
template <typename T>
struct Point2d{
T x, y;
Point2d(){}
Point2d(T _x, T _y): x(_x), y(_y) {}
};
template <typename T>
struct Vector2d{
Point2d<T> p1, p2;
Vector2d(Point2d<T> _p1, Point2d<T> _p2): p1(_p1), p2(_p2) {}
Vector2d(T x1, T y1, T x2, T y2){
this->p1.x=x1;
this->p1.y=y1;
this->p2.x=x2;
this->p2.y=y2;
}
Vector2d<T> operator+(Vector2d<T> other){
return Vector2d<T>(this->p1, other.p2);
}
T AbsOuter(Vector2d<T> other){
T x1=this->p2.x-this->p1.x;
T y1=this->p2.y-this->p1.y;
T x2=other.p2.x-other.p1.x;;
T y2=other.p2.y-other.p1.y;
return x1*y2-x2*y1;
}
};
template <typename T>
T Direction(Point2d<T> p1, Point2d<T> p2, Point2d<T> p3){
Vector2d<T> v1(p1, p3);
Vector2d<T> v2(p1, p2);
return v1.AbsOuter(v2);
}
template <typename T>
bool OnSegment(Point2d<T> p1, Point2d<T> p2, Point2d<T> p3){
if(std::min(p1.x, p2.x)<=p3.x && std::max(p1.x, p2.x)>=p3.x
&& std::min(p1.y, p2.y)<=p3.y && std::max(p1.y, p2.y)>=p3.y) return true;
else return false;
}
template <typename T>
bool SegmentsIntersect(Point2d<T> p1, Point2d<T> p2, Point2d<T> p3, Point2d<T> p4){
T d1, d2, d3, d4;
d1=Direction(p3, p4, p1);
d2=Direction(p3, p4, p2);
d3=Direction(p1, p2, p3);
d4=Direction(p1, p2, p4);
if( ((d1>0 && d2<0) || (d1<0 && d2>0)) &&
((d3>0 && d4<0) || (d3<0 && d4>0)) ) return true;
else if(d1==0 && OnSegment(p3, p4, p1)) return true;
else if(d2==0 && OnSegment(p3, p4, p2)) return true;
else if(d3==0 && OnSegment(p1, p2, p3)) return true;
else if(d4==0 && OnSegment(p1, p2, p4)) return true;
else return false;
}
int main(void){
Point2d<double> p1(3, 4);
Point2d<double> p2(0, 5);
Point2d<double> p3(-1, 2);
Point2d<double> p4(5, 6);
Vector2d<double> v1(p1, p2);
Vector2d<double> v2(p3, p4);
bool isIntersect=SegmentsIntersect(p1, p2, p3, p4);
std::cout<<"is Intersect: "<<isIntersect<<std::endl;
return 0;
}